Remove N-th Node from End of List - LeetCode 19

question

• 刪除鏈表中倒數第 n 個節點，回傳新的頭節點。

thoughts

• 使用雙指針：
• 先讓 fast 前進 n 步，再讓 slow 和 fast 一起走。
• 當 fast 到尾時，slow 剛好在倒數第 n 的前一個節點。
• 注意刪除頭節點的特殊情況，可以用 dummy node 簡化。
• 時間：O(n)
• 空間：O(1)

kotlin

fun removeNthFromEnd(head: ListNode?, n: Int): ListNode? {
    val dummy = ListNode(0)
    dummy.next = head
    var fast: ListNode? = dummy
    var slow: ListNode? = dummy

    repeat(n + 1) { fast = fast?.next }

    while (fast != null) {
        fast = fast.next
        slow = slow?.next
    }

    slow?.next = slow?.next?.next
    return dummy.next
}

follow up

• 如果要多次刪除倒數第 n 個節點，能否優化？
• 如果鏈表長度未知且只能單次遍歷，該怎麼做？
• 如果 n 的值可能比鏈表長度還大，要如何處理？